home *** CD-ROM | disk | FTP | other *** search
/ Aminet 24 / Aminet 24 (1998)(GTI - Schatztruhe)[!][Apr 1998].iso / Aminet / comm / mail / Mutt089src.lha / Mutt-0.89i-AMIGA / src / rx / rxgnucomp.c < prev    next >
C/C++ Source or Header  |  1998-01-28  |  44KB  |  1,666 lines
  1. /*    Copyright (C) 1992, 1993, 1994, 1995 Free Software Foundation, Inc.
  2.  * 
  3.  * This program is free software; you can redistribute it and/or modify
  4.  * it under the terms of the GNU Library General Public License as published by
  5.  * the Free Software Foundation; either version 2, or (at your option)
  6.  * any later version.
  7.  * 
  8.  * This program is distributed in the hope that it will be useful,
  9.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11.  * GNU Library General Public License for more details.
  12.  * 
  13.  * You should have received a copy of the GNU Library General Public License
  14.  * along with this software; see the file COPYING.  If not, write to
  15.  * the Free Software Foundation, 59 Temple Place - Suite 330, 
  16.  * Boston, MA 02111-1307, USA. 
  17.  */
  18.  
  19.  
  20. #include <sys/types.h>
  21. #include "rxall.h"
  22. #include "rxgnucomp.h"
  23. #include "inst-rxposix.h"
  24.  
  25.  
  26. /* {A Syntax Table} 
  27.  */
  28.  
  29. /* Define the syntax basics for \<, \>, etc.
  30.  */
  31.  
  32. #ifndef emacs
  33. #define CHARBITS 8
  34. #define CHAR_SET_SIZE (1 << CHARBITS)
  35. #define Sword 1
  36. #define SYNTAX(c) re_syntax_table[c]
  37. char re_syntax_table[CHAR_SET_SIZE];
  38.  
  39. #ifdef __STDC__
  40. static void
  41. init_syntax_once (void)
  42. #else
  43. static void
  44. init_syntax_once ()
  45. #endif
  46. {
  47.    register int c;
  48.    static int done = 0;
  49.  
  50.    if (done)
  51.      return;
  52.  
  53.    rx_bzero ((char *)re_syntax_table, sizeof re_syntax_table);
  54.  
  55.    for (c = 'a'; c <= 'z'; c++)
  56.      re_syntax_table[c] = Sword;
  57.  
  58.    for (c = 'A'; c <= 'Z'; c++)
  59.      re_syntax_table[c] = Sword;
  60.  
  61.    for (c = '0'; c <= '9'; c++)
  62.      re_syntax_table[c] = Sword;
  63.  
  64.    re_syntax_table['_'] = Sword;
  65.  
  66.    done = 1;
  67. }
  68. #endif /* not emacs */
  69.  
  70.  
  71.  
  72.  
  73.  
  74. const char *rx_error_msg[] =
  75. {
  76.   0,                        /* REG_NOUT */
  77.   "No match",                    /* REG_NOMATCH */
  78.   "Invalid regular expression",            /* REG_BADPAT */
  79.   "Invalid collation character",        /* REG_ECOLLATE */
  80.   "Invalid character class name",        /* REG_ECTYPE */
  81.   "Trailing backslash",                /* REG_EESCAPE */
  82.   "Invalid back reference",            /* REG_ESUBREG */
  83.   "Unmatched [ or [^",                /* REG_EBRACK */
  84.   "Unmatched ( or \\(",                /* REG_EPAREN */
  85.   "Unmatched \\{",                /* REG_EBRACE */
  86.   "Invalid content of \\{\\}",            /* REG_BADBR */
  87.   "Invalid range end",                /* REG_ERANGE */
  88.   "Memory exhausted",                /* REG_ESPACE */
  89.   "Invalid preceding regular expression",    /* REG_BADRPT */
  90.   "Premature end of regular expression",    /* REG_EEND */
  91.   "Regular expression too big",            /* REG_ESIZE */
  92.   "Unmatched ) or \\)",                /* REG_ERPAREN */
  93. };
  94.  
  95.  
  96.  
  97. /* 
  98.  * Macros used while compiling patterns.
  99.  *
  100.  * By convention, PEND points just past the end of the uncompiled pattern,
  101.  * P points to the read position in the pattern.  `translate' is the name
  102.  * of the translation table (`TRANSLATE' is the name of a macro that looks
  103.  * things up in `translate').
  104.  */
  105.  
  106.  
  107. /*
  108.  * Fetch the next character in the uncompiled pattern---translating it 
  109.  * if necessary. *Also cast from a signed character in the constant
  110.  * string passed to us by the user to an unsigned char that we can use
  111.  * as an array index (in, e.g., `translate').
  112.  */
  113. #define PATFETCH(c)                            \
  114.  do {if (p == pend) return REG_EEND;                    \
  115.     c = (unsigned char) *p++;                        \
  116.     c = translate[c];                             \
  117.  } while (0)
  118.  
  119. /* 
  120.  * Fetch the next character in the uncompiled pattern, with no
  121.  * translation.
  122.  */
  123. #define PATFETCH_RAW(c)                            \
  124.   do {if (p == pend) return REG_EEND;                    \
  125.     c = (unsigned char) *p++;                         \
  126.   } while (0)
  127.  
  128. /* Go backwards one character in the pattern.  */
  129. #define PATUNFETCH p--
  130.  
  131.  
  132. #define TRANSLATE(d) translate[(unsigned char) (d)]
  133.  
  134. typedef int regnum_t;
  135.  
  136. /* Since offsets can go either forwards or backwards, this type needs to
  137.  * be able to hold values from -(MAX_BUF_SIZE - 1) to MAX_BUF_SIZE - 1.
  138.  */
  139. typedef int pattern_offset_t;
  140.  
  141. typedef struct
  142. {
  143.   struct rexp_node ** top_expression;
  144.   struct rexp_node ** last_expression;
  145.   struct rexp_node ** last_non_regular_expression;
  146.   pattern_offset_t inner_group_offset;
  147.   regnum_t regnum;
  148. } compile_stack_elt_t;
  149.  
  150. typedef struct
  151. {
  152.   compile_stack_elt_t *stack;
  153.   unsigned size;
  154.   unsigned avail;            /* Offset of next open position.  */
  155. } compile_stack_type;
  156.  
  157.  
  158. #define INIT_COMPILE_STACK_SIZE 32
  159.  
  160. #define COMPILE_STACK_EMPTY  (compile_stack.avail == 0)
  161. #define COMPILE_STACK_FULL  (compile_stack.avail == compile_stack.size)
  162.  
  163. /* The next available element.  */
  164. #define COMPILE_STACK_TOP (compile_stack.stack[compile_stack.avail])
  165.  
  166.  
  167. /* Set the bit for character C in a list.  */
  168. #define SET_LIST_BIT(c)                               \
  169.   (b[((unsigned char) (c)) / CHARBITS]               \
  170.    |= 1 << (((unsigned char) c) % CHARBITS))
  171.  
  172. /* Get the next unsigned number in the uncompiled pattern.  */
  173. #define GET_UNSIGNED_NUMBER(num)                     \
  174.   { if (p != pend)                            \
  175.      {                                    \
  176.        PATFETCH (c);                             \
  177.        while (isdigit (c))                         \
  178.          {                                 \
  179.            if (num < 0)                            \
  180.               num = 0;                            \
  181.            num = num * 10 + c - '0';                     \
  182.            if (p == pend)                         \
  183.               break;                             \
  184.            PATFETCH (c);                        \
  185.          }                                 \
  186.        }                                 \
  187.     }        
  188.  
  189. #define CHAR_CLASS_MAX_LENGTH  64
  190.  
  191. #define IS_CHAR_CLASS(string)                        \
  192.    (!strcmp (string, "alpha") || !strcmp (string, "upper")        \
  193.     || !strcmp (string, "lower") || !strcmp (string, "digit")        \
  194.     || !strcmp (string, "alnum") || !strcmp (string, "xdigit")        \
  195.     || !strcmp (string, "space") || !strcmp (string, "print")        \
  196.     || !strcmp (string, "punct") || !strcmp (string, "graph")        \
  197.     || !strcmp (string, "cntrl") || !strcmp (string, "blank"))
  198.  
  199.  
  200. /* These predicates are used in regex_compile. */
  201.  
  202. /* P points to just after a ^ in PATTERN.  Return true if that ^ comes
  203.  * after an alternative or a begin-subexpression.  We assume there is at
  204.  * least one character before the ^.  
  205.  */
  206.  
  207. #ifdef __STDC__
  208. static int
  209. at_begline_loc_p (const char *pattern, const char * p, unsigned long syntax)
  210. #else
  211. static int
  212. at_begline_loc_p (pattern, p, syntax)
  213.      const char *pattern;
  214.      const char * p;
  215.      unsigned long syntax;
  216. #endif
  217. {
  218.   const char *prev = p - 2;
  219.   int prev_prev_backslash = ((prev > pattern) && (prev[-1] == '\\'));
  220.   
  221.     return
  222.       
  223.       (/* After a subexpression?  */
  224.        ((*prev == '(') && ((syntax & RE_NO_BK_PARENS) || prev_prev_backslash))
  225.        ||
  226.        /* After an alternative?  */
  227.        ((*prev == '|') && ((syntax & RE_NO_BK_VBAR) || prev_prev_backslash))
  228.        );
  229. }
  230.  
  231. /* The dual of at_begline_loc_p.  This one is for $.  We assume there is
  232.  * at least one character after the $, i.e., `P < PEND'.
  233.  */
  234.  
  235. #ifdef __STDC__
  236. static int
  237. at_endline_loc_p (const char *p, const char *pend, int syntax)
  238. #else
  239. static int
  240. at_endline_loc_p (p, pend, syntax)
  241.      const char *p;
  242.      const char *pend;
  243.      int syntax;
  244. #endif
  245. {
  246.   const char *next = p;
  247.   int next_backslash = (*next == '\\');
  248.   const char *next_next = (p + 1 < pend) ? (p + 1) : 0;
  249.   
  250.   return
  251.     (
  252.      /* Before a subexpression?  */
  253.      ((syntax & RE_NO_BK_PARENS)
  254.       ? (*next == ')')
  255.       : (next_backslash && next_next && (*next_next == ')')))
  256.     ||
  257.      /* Before an alternative?  */
  258.      ((syntax & RE_NO_BK_VBAR)
  259.       ? (*next == '|')
  260.       : (next_backslash && next_next && (*next_next == '|')))
  261.      );
  262. }
  263.  
  264.  
  265. unsigned char rx_id_translation[256] =
  266. {
  267.   0,  1,  2,  3,  4,  5,  6,  7,  8,  9,
  268.  10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
  269.  20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
  270.  30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
  271.  40, 41, 42, 43, 44, 45, 46, 47, 48, 49,
  272.  50, 51, 52, 53, 54, 55, 56, 57, 58, 59,
  273.  60, 61, 62, 63, 64, 65, 66, 67, 68, 69,
  274.  70, 71, 72, 73, 74, 75, 76, 77, 78, 79,
  275.  80, 81, 82, 83, 84, 85, 86, 87, 88, 89,
  276.  90, 91, 92, 93, 94, 95, 96, 97, 98, 99,
  277.  
  278.  100, 101, 102, 103, 104, 105, 106, 107, 108, 109,
  279.  110, 111, 112, 113, 114, 115, 116, 117, 118, 119,
  280.  120, 121, 122, 123, 124, 125, 126, 127, 128, 129,
  281.  130, 131, 132, 133, 134, 135, 136, 137, 138, 139,
  282.  140, 141, 142, 143, 144, 145, 146, 147, 148, 149,
  283.  150, 151, 152, 153, 154, 155, 156, 157, 158, 159,
  284.  160, 161, 162, 163, 164, 165, 166, 167, 168, 169,
  285.  170, 171, 172, 173, 174, 175, 176, 177, 178, 179,
  286.  180, 181, 182, 183, 184, 185, 186, 187, 188, 189,
  287.  190, 191, 192, 193, 194, 195, 196, 197, 198, 199,
  288.  
  289.  200, 201, 202